A basic problem in communications and data storage involves determining whether information received at a receiver accurately reflects information transmitted from a transmitter. Conventionally, additional verification bits (e.g., parity bits, cyclic redundancy check bits) have been added to message bits to facilitate improving confidence that a received message matches a transmitted message. The communication/data storage system, therefore typically includes an Error-Correcting Code (ECC). For example, in the encoding process, the codeword of an ECC code is constructed by adding redundancy/check bits to the data field. Low density parity check (LDPC) codes define one type of ECC.
LDPC codes are linear block codes associated with a sparse parity check matrix that can be represented as a bipartite graph. The sparsity refers to a condition where a parity check matrix for an LDPC code may be constrained to have less than a certain number of ones per column and to have less than a certain number of ones per row.
An LDPC decoder receives a vector (received vector), attempts to decode the most likely codeword corresponding to the received vector, and reports on whether the decoder vector is a valid codeword. An LDPC codeword may include message bits and redundancy bits. The redundancy bits may be, for example, parity bits. An LDPC code may be a linear (N,K) block code with K information bits mapped to a codeword of block length N. An LDPC code C can be specified in terms of a low-density (e.g., sparse) N×K binary parity check matrix. While examples are provided in terms of binary codes herein, it should be understood that similar methodologies can be applied to non-binary codes, where the word “bit” is replaced by the word “non-binary symbol”.
A codeword can be decoded and verified in pieces where beliefs are built up about certain pieces of the codeword and then those beliefs are used to decode other pieces of the codeword. Decoding will continue until the constraints for a codeword have been satisfied, until a maximum number of tries (e.g., iterations through an LDPC decoder) have been attempted, or until other criteria terminate decoding.
One type of LDPC decoder is a layered decoder. FIG. 1 illustrates one example of a conventional layered decoder 10. The layered decoder 10 provides a convergence flag when the convergence verification unit 12 determines that the layered decoder 10 has converged on a decision concerning decoding a codeword. The convergence verification unit 12 will accept a syndrome input from a syndrome computation unit 20 and will also accept a hard decision (“HD”) change input from an HD tracking unit 22. The syndrome and HD change signals can be combined to determine whether the layered LDPC decoder 10 has reached convergence. The syndrome computation unit 20 computes the syndromes of a current layer in the layered decoder 10 based on whether all check nodes in the layer are satisfied. The HD tracking unit 22 can verify whether the updated HD has changed its value compared to the previous update of the same bit (variable) node. The update will have been performed in a layer that was processed earlier.
The syndrome computation unit 20 and the HD tracking unit 22 receive an updated HD from a logic 30 that is responsible for processing and/or updating bit nodes and check nodes. The logic 30 also provides updated R messages to an R memory 14 and provides updated Q or P messages to a Q or P memory 16. The logic 30 receives values from the R memory 14 and the Q or P memory 16.
Conventionally, a layered decoder like layered LDPC decoder 10 may have L layers, L being an integer. A conventional decoder may go around and around through processing layers until L layers in a row report that the syndromes are all satisfied and until there have been no HD changes for L layers in a row. In a standard convergence unit 12, a layer count may only be incremented up towards L if all the HD change flags indicated that the HD had not changed and if the current syndrome is satisfied. If either an HD changed, or a syndrome was not satisfied, then the layer count may not be incremented up towards L, and/or may be reset all the way to zero. If the layer count ever reaches L, then the decoder 10 can stop and report convergence. However, this convergence technique is not optimal.
In one layered approach, different layers may be tasked with providing different partial decoding results. In one example, a syndrome is a function (e.g., binary addition) of all the variable node values in the bipartite graph that are connected to the same check node. The syndrome calculation involves verifying the parity checks of the current HD values (current decoded vector). A non-zero syndrome vector may signal some number of erroneous HD values. In one example, bi is a binary sequence corresponding to the bits connected to the check nodes at layer i. Syndrome Si=ATbi is the syndrome of layer i, where A is the parity check matrix of the layer i (this is a submatrix of the LDPC parity check matrix) and T is the transpose of a matrix. A layered decoder may sequentially decode given syndromes Si from the top layer to the bottom layer, and then return to the top layer to complete additional iterations, using previous decoding results to update the log likelihood ratios (LLRs) for each node or edge in the decoder graph until decoding is completed.
Conventional convergence logic for a layered decoder is sub-optimal because all layers of the layered LDPC decoder are considered and/or reconsidered before convergence can be determined. Conventionally, in a layered LDPC decoder, a syndrome update occurs in the current layer of the layered decoder. To finish updating an entire syndrome at least once for all layers requires running through at least one entire iteration of LDPC decoding. When a bit is flipped (e.g., corrected) during layered decoding, conventional decoders may cycle through yet another entire iteration of the decoder to insure that all syndromes are satisfied before reporting convergence. This may waste time and power.
Completing yet another entire iteration through a layered decoder may be wasteful when a correct codeword may be successfully and conclusively decoded in the current iteration. Also, in some instances, a correct codeword may be decoded after just a few layers in a layered decoder when, for example, the received vectors (e.g., LLRs) are correct or nearly correct.
FIG. 2 illustrates example convergence detection with conventional standard convergence logic in a conventional layered decoder 50. The current HD for a column J for a circulant 52, prior to processing at layer i, is the HD produced during the processing for a circulant 51 at layer i−3. During the processing of layer i, some HD for block column J may change due to updates obtained while processing circulant 52. It may take L−3 layers after layer i is processed to actually detect that the decoder 50 arrived at a valid codeword at layer i. This is sub-optimal.
LDPC codes are designed to have a structured parity check matrix to facilitate enhancing efficiency in storage (e.g., memory) and processing (e.g., encoder, decoder) units. An LDPC encoder takes in a word of length K and outputs a codeword of length N by inserting N−K redundancy bits. The encoder adds the bits as a function of an LDPC code.